// https://www.lintcode.com/problem/the-skyline-problem/description

class Event {
public:
    int x;
    int h;
    int type; // enter = +1, exit = -1
    
    Event(int x_, int h_, int type_) {
        x = x_;
        h = h_;
        type = type_;
    }
    
    bool operator < (const Event &other) const {
        // return this->x < other.x || (this->x == other.x && this->type > other.type); 
        //注意-1和1别反了；height也需要排序
// [[1,2,3],[1,2,4],[1,2,3],[1,2,4]]
// Output
// [[1,1,3],[1,2,4]]
// Expected
// [[1,2,4]]
        
        return this->x < other.x || (this->x == other.x && 
            this->type * this->h > other.type * other.h);
    }
};

class Solution {
public:
    /**
     * @param buildings: A list of lists of integers
     * @return: Find the outline of those buildings
     */
    vector<vector<int>> buildingOutline(vector<vector<int>> &buildings) {
        vector<Event> events;
        for (int i = 0; i < buildings.size(); i++) {
            // vector<int> b = buildings[i];
            const auto& b = buildings[i];
            events.push_back(Event(b[0], b[2], 1)); //进入1 退出-1
            events.push_back(Event(b[1], b[2], -1));
        }
        
        sort(events.begin(), events.end());
        multiset<int> height; //priority_queue删除中间元素没有multiset方便
        vector<vector<int>> rec;
        // for (Event e: events) {
        for (const auto& e: events) {
            if (e.type == 1) {
                int maxHeight = height.empty()? 0:*height.rbegin();
                if (e.h > maxHeight) {
                    rec.push_back({e.x, e.h});
                }
                height.insert(e.h);
            }
            if (e.type == -1) {
                height.erase(height.find(e.h));
                int maxHeight = height.empty()? 0:*height.rbegin();
                if (e.h > maxHeight) {
                    rec.push_back({e.x, maxHeight});
                }
            }
            
        }
        vector<vector<int>> ans;
        // for (int i = 1; i < ans.size(); ++i) { !!!
        for (int i = 1; i < rec.size(); ++i) {
            if (rec[i - 1][1] != 0) {
                ans.push_back({rec[i - 1][0], rec[i][0], rec[i - 1][1]});
            }
        }
        return ans;
    }
};


class Event {
public:
    int x;
    int h;
    int type;
    Event(int x, int h, int type) {
        this->x = x;
        this->h = h;
        this->type = type;
    }
    bool operator < (const Event& e) const {
        return this->x < e.x || (this->x == e.x && this->h * this->type > e.h * e.type); 
        //如果h相同，type是1的排在前面；如果h不同，如果type为1，高的排在前面。如果type为-1，矮的排在前面。
    }
};
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<Event> events;
        vector<vector<int>> rec;
        for (auto& a: buildings) {
            events.push_back(Event(a[0], a[2], 1));
            events.push_back(Event(a[1], a[2], -1));
        }
        sort(events.begin(), events.end());
        multiset<int> height;
        for (auto& e: events) {
            int maxHeight = height.empty()? 0: *height.rbegin();
            if (e.type == 1) {
                height.insert(e.h);
            } else {
                height.erase(height.find(e.h));
            }
            int newMaxHeight = height.empty()? 0: *height.rbegin();
            if (newMaxHeight != maxHeight) // maxHeight发生变化，就是拐点
                rec.push_back({e.x, newMaxHeight});
        }
        return rec;
    }
};